package org.liaohailong.helloworld.practice;

import java.util.Arrays;

/**
 * Author: liaohailong
 * Time: 2021/6/7 09:21
 * Describe: 初级算法 - 字符串练习
 */
public class StringPractice {

    // LC 反转字符串
    public void reverseString(char[] s) {
        int i = 0, j = s.length - 1;
        while (i < j) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
            i++;
            j--;
        }
    }

    // LC 整数反转
//    public int reverse(int x) {
//        String xStr = String.valueOf(x);
//        boolean negative = xStr.startsWith("-");
//        if (negative) xStr = xStr.substring(1);
//        char[] chars = xStr.toCharArray();
//        reverseString(chars);
//        String reverseStr = String.valueOf(chars);
//        try {
//            int result = Integer.parseInt(reverseStr);
//            return negative ? -result : result;
//        } catch (Exception e) {
//            return 0;
//        }
//    }

    // LC 整数反转
    public int reverse(int x) {
        long res = 0;
        while (x != 0) {
            int a = x % 10;
            res = res * 10 + a;
            x /= 10;
        }
        return (int) res == res ? (int) res : 0;
    }

    // LC 字符串中的第一个唯一字符
//    @RequiresApi(api = Build.VERSION_CODES.N)
//    public int firstUniqChar(String s) {
//        char[] chars = s.toCharArray();
//        HashMap<Character, Integer> cache = new HashMap<>();
//        for (char c : chars) cache.put(c, cache.getOrDefault(c, 0) + 1);
//        for (int i = 0; i < chars.length; i++) {
//            Integer count = cache.get(chars[i]);
//            if (count != null && count < 2) return i;
//        }
//        return -1;
//    }

    // LC 字符串中的第一个唯一字符
    public int firstUniqChar(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.indexOf(s.charAt(i)) == s.lastIndexOf(s.charAt(i)))
                return i;
        }
        return -1;
    }

    // LC 有效的字母异位词
//    public boolean isAnagram(String s, String t) {
//        if (s.length() != t.length()) return false;
//        int[][] cache = new int[26][1];
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            int index = c - 'a';
//            cache[index][0] += 1;
//        }
//        for (int i = 0; i < t.length(); i++) {
//            char c = t.charAt(i);
//            int index = c - 'a';
//            if (cache[index][0] <= 0) return false;
//            cache[index][0] -= 1;
//        }
//        return true;
//    }

    // LC 有效的字母异位词
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        Arrays.sort(sc);
        Arrays.sort(tc);
        return Arrays.equals(sc, tc);
    }

    // LC 验证回文串
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        // 保留字母
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)) {
                sb.append(c);
            }
        }
        s = sb.toString().toLowerCase();
        char[] chars = s.toCharArray();
        int i = 0, j = chars.length - 1;
        while (i < j) {
            if (chars[i] != chars[j]) return false;
            i++;
            j--;
        }
        return true;
    }

    // LC 字符串转换整数 (atoi)
    public int myAtoi(String s) {
        char[] chars = s.toCharArray();
        int start = -1;
        int end = -1;
        for (int i = 0; i < chars.length; i++) {
            if (Character.isDigit(chars[i])) {
                if (start == -1) {
                    start = i;
                    end = start;
                } else end++;
            } else {
                if (chars[i] == '-' || chars[i] == '+') {
                    if (start == -1) {
                        start = i;
                        end = start;
                    } else break;
                } else if (chars[i] != ' ' || start != -1) break;
            }
        }
        // 无效输入
        if (start == -1) return 0;

        char c = chars[start];
        boolean negative = false;
        if (c == '-' || c == '+') {
            start += 1;
            if (c == '-') negative = true;
        }
        // 无效数字
        if (start >= end + 1) return 0;

        // 值超出Integer最大值直接返回
        while (start < chars.length && chars[start] == '0') start++; // 首位0移除
        int count = end + 1 - start;
        if (count <= 0) return 0; // 全部都是0
        int maxCount = String.valueOf(Integer.MAX_VALUE).length();
        if (count > maxCount) {
            return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }

        // 用Long转一下，判断大小
        long longVal = Long.parseLong(s.substring(start, end + 1));
        longVal = negative ? -longVal : longVal;
        // 超过界限，取边界值返回
        if (longVal < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        } else if (longVal > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else {
            return (int) longVal;
        }
    }

    // LC 字符串转换整数 (atoi)
//    public int myAtoi(String s) {
//        if (s.length() < 1) return 0;
//        // 截取出有效字符范围
//        int start = 0;
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if (Character.isDigit(c) || c == '-' || c == '+') {
//                start = i;
//                break;
//            } else if (c != ' ') break; // 过滤空格开头
//        }
//
//        // 无效字符判断
//        char first = s.charAt(start);
//        if (!Character.isDigit(first) && first != '-' && first != '+') return 0;
//
//        int end = start;
//        for (int i = start + 1; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if (Character.isDigit(c)) {
//                end++;
//            } else break;
//        }
//
//        // 单字符或无效字符
//        if (start == end) {
//            char c = s.charAt(start);
//            boolean digit = Character.isDigit(c);
//            return digit ? Character.digit(c, 10) : 0;
//        }
//
//        // 移除开头无效字符0
//        while (start < s.length() && s.charAt(start) == '0') start++;
//        // 值为0的字符
//        if (start >= end) {
//            start = Math.min(start, s.length() - 1);
//            char c = s.charAt(start);
//            boolean digit = Character.isDigit(c);
//            return digit ? Character.digit(c, 10) : 0;
//        }
//
//        // 移除符号
//        boolean negative = false;
//        if (s.charAt(start) == '-' || s.charAt(start) == '+') {
//            if (s.charAt(start) == '-') negative = true;
//            start++;
//        }
//
//        // 移除开头无效字符0
//        while (start < s.length() && s.charAt(start) == '0') start++;
//        // 值为0的字符
//        if (start >= end) {
//            start = Math.min(start, s.length() - 1);
//            char c = s.charAt(start);
//            boolean digit = Character.isDigit(c);
//            int res = digit ? Character.digit(c, 10) : 0;
//            return negative ? -res : res;
//        }
//
//        String MAX = Integer.toString(Integer.MAX_VALUE);
//        int count = end - start + 1;
//        if (count > MAX.length()) {
//            return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
//        }
//
//        long val = Long.parseLong(s.substring(start, end + 1));
//        val = negative ? -val : val;
//        if (val < Integer.MIN_VALUE) return Integer.MIN_VALUE;
//        if (val > Integer.MAX_VALUE) return Integer.MAX_VALUE;
//        return (int) (val);
//    }

    // LC 实现 strStr()
    public int strStr(String haystack, String needle) {
        int hl = haystack.length();
        int nl = needle.length();
        if (nl <= 0) return 0;
        if (hl <= 0) return -1;
        if (nl > hl) return -1;
        int i = 0, j = 0;
        while (i < hl && j < nl) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        return j == nl ? i - j : -1;
    }

    // LC 外观数列
    public String countAndSay(int n) {
        String str = "1";
        if (n == 1) return str;
        while (n-- > 1) {
            int time = 0;
            StringBuilder sb = new StringBuilder();
            Character last = null;
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if (last == null) {
                    time++;
                } else if (last == c) {
                    time++;
                } else {
                    // 几个
                    sb.append(time);
                    // 什么
                    sb.append(last);
                    // 新的一个
                    time = 1;
                }
                last = c;
            }
            // last but not least
            if (time > 0) {
                // 几个
                sb.append(time);
                // 什么
                sb.append(last);
            }
            str = sb.toString();
        }

        return str;
    }


    // LC 最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        // 按长度排序
        Arrays.sort(strs, (o1, o2) -> Integer.compare(o1.length(), o2.length()));
        int minLength = strs[0].length();
        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < minLength) {
            Character head = null;
            for (String str : strs) {
                char c = str.charAt(i);
                if (head == null) head = c;
                else if (head != c) {
                    head = null;
                    break;
                }
            }
            if (head != null) sb.append(head);
            else break;
            i++;
        }
        return sb.toString();
    }
}
